from functools import cache
# 记忆化搜索
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        if n < m:
            return 0

        @cache
        # 有三种递归情况，
        # 字符相等，1，选  2，不选
        # 字符相等也可以不选，因为后面也可能有相等的情况
        # 字符不相等，3， 不选
        def dfs(i, j):
            # 如果t 已经匹配完，说明找到一个子序列，返回1
            if j == m:
                return 1
            if i == n and j < m:
                return 0
            # 情况1：当前字符串匹配，继续下一个字符
            if s[i] == t[j]:
                # 两种选择，一种选，一种不选，进行下一个字符
                return dfs(i + 1, j + 1) + dfs(i + 1, j)
            # 情况二：当前字符不匹配，继续在s中找下一个字符
            return dfs(i + 1, j)

        return dfs(0, 0)


# 动态规划
        # 记忆化搜索 一比一 翻译转为dp
        n, m = len(s), len(t)
        if n < m:
            return 0
        # 动态规划
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        # 初始化dp 当t 为 空字符串时，s中任意子串都有一种方式匹配到空字符串
        for i in range(n + 1):
            dp[i][m] = 1

        # 倒叙遍历，状态转移方程里使用了 dp[i + 1][j + 1] 和 dp[i + 1][j]，
        # 这就要求在计算 dp[i][j] 之前，dp[i + 1][j + 1] 和 dp[i + 1][j]
        # 已经计算好，所以应该采用倒序遍历。
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                if s[i] == t[j]:
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j]
                else:
                    dp[i][j] = dp[i + 1][j]
        return dp[0][0]

# 动态规划
        n = len(triangle)
        # f 的每一行长度与三角形对应行的长度相同
        f=[[0]*(i+1) for i in range(n)]
        # 讲f的最后一行初始化为三角形的最后一行
        # 因为从最后一行的每个位置到底部的最小路径和就是该位置的值本身
        f[-1]=triangle[-1]
        # 从倒是第二行开始向上遍历三角形的每一行
        for i in range(n-2, -1, -1):
            # 遍历当前行的每个元素及其索引
            for j,x in enumerate(triangle[i]):
                f[i][j]=min(f[i+1][j],f[i+1][j+1])+x
        return f[0][0]
